#include "esbtree.h"

static void esbtree_split_leafnode(esbt_tree * esbtree, bt_node * node);
static void esbtree_split_innernode(esbt_tree * esbtree, short level);
static short es_get_split_point(esbt_tree * esbtree, bt_node * node);
static void esbtree_insert_leaf(bt_node * node, bt_entry * entry);
static void esbtree_insert_inner(bt_node * parent, bt_entry * entry, bt_node * left, bt_node * right, short level);


void esbtree_insert_leaf(bt_node * node, bt_entry * entry)
{
	for(short i = node->entry_active - 1; i >= es_index_trace[0]; i--)
		node->entries[i + 1] = node->entries[i];
	node->entries[es_index_trace[0]] = entry;
	node->entry_active++;
}

void esbtree_insert_inner(bt_node * parent, bt_entry * entry, bt_node * left, bt_node * right, short level)
{
	short position = es_index_trace[level];
	for(short i = parent->entry_active; i > position; i--)
	{
		parent->entries[i] = parent->entries[i - 1];
		parent->children[i + 1] = parent->children[i];
	}
	parent->entries[position] = entry;
	parent->children[position] = left;
	parent->children[position + 1] = right;
	parent->entry_active++;
}

esbt_tree * esbtree_create(short order)
{
	esbt_tree * esbtree = (esbt_tree *)malloc(sizeof(esbt_tree));
	esbtree->order = order;
	esbtree->root = allocate_btree_node(order, (short)0);
	esbtree->his = his_init(WIDTH, MAX_KEY_VALUE / WIDTH);
	esbtree->stat = stat_init(MAX_TREE_LEVEL);
	memset(es_index_trace, 0, sizeof(es_index_trace));
	for(short i = 0; i < MAX_TREE_LEVEL; i++)
		es_node_trace[i] = (bt_node *)malloc(sizeof(bt_node));
	return esbtree;
}

void esbtree_search(esbt_tree * esbtree, bt_entry * entry, bt_entry * search_result)
{
	bt_node * node = esbtree->root;
	short level_index;
	for(short i = esbtree->root->node_level; i > 0; i--)
	{
		level_index = binary_search_greater(node->entries, node->entry_active, entry);
		node = node->children[level_index];
		es_index_trace[i] = level_index;
	}
	level_index = binary_search_euqal(node->entries, node->entry_active, entry);
	es_index_trace[0] = level_index;
	if(level_index == -1)
		search_result = NULL;
	else
	{
		search_result->key = node->entries[level_index]->key;
		search_result->value = node->entries[level_index]->value;
	}
}

bool need_split(esbt_tree * esbtree, int level)
{
	if(level == esbtree->root->node_level)
		return false;
	int left = 0, right = MAX_KEY_VALUE - 1;

	for (int i = level + 1; i < esbtree->root->node_level + 1; i++)
	{
		if(es_index_trace[i] != 0)
		{
			left = (int)(es_node_trace[i]->entries[es_index_trace[i] - 1]->key);
			break;
		}
	}

	for (int i = level + 1; i < esbtree->root->node_level + 1; i++)
	{
		if(es_index_trace[i] != es_node_trace[i]->entry_active)
		{
			right = (int)(es_node_trace[i]->entries[es_index_trace[i]]->key);
			break;
		}
	}
	
	if(his_range_ratio(esbtree->his, left, right) > (double)20/(double)esbtree->stat->node_num[level])
		return true;
	return false;
}

void get_esbtree_node(esbt_tree * esbtree, short * index)
{
	bt_node * node = esbtree->root;
	es_node_trace[node->node_level] = esbtree->root;
	for(short i = esbtree->root->node_level - 1; i >= 0; i--)
	{
		node = node->children[index[i + 1]];
		es_node_trace[i] = node;
	}
}

void esbtree_insert(esbt_tree * esbtree, bt_entry * entry)
{
	bt_node * node = esbtree->root;
	short level_index;
	for(short i = esbtree->root->node_level; i > 0; i--)
	{
		level_index = binary_search_greater(node->entries, node->entry_active, entry);
		node = node->children[level_index];
		es_index_trace[i] = level_index;
	}

	level_index = binary_search_greater(node->entries, node->entry_active, entry);
	es_index_trace[0] = level_index;

	//if(es_index_trace[0] >= 1 && node->entries[es_index_trace[0] - 1]->key == entry->key)
	//	return;

	esbtree_insert_leaf(node, entry);
	get_esbtree_node(esbtree, es_index_trace);

	if(IS_NODE_FULL(esbtree, node))
		esbtree_split_leafnode(esbtree, node);
	else if(IS_NODE_HALF_FULL(esbtree, node))
	{
		if(need_split(esbtree, 0))
			esbtree_split_leafnode(esbtree, node);
	}
	his_insert(esbtree->his, (int)(entry->key));
	stat_addkey(esbtree->stat);
}

void esbtree_delete(esbt_tree * esbtree, bt_entry * entry)
{

}

void esbtree_destroy(esbt_tree * esbtree)
{

}

static short es_get_split_point(esbt_tree * esbtree, bt_node * node)
{
	short index = node->entry_active >> 1;
	for(short i = 1; i < index + 1; i++)
	{
		if(node->entries[index - i]->key != node->entries[index]->key)
			return index - i + 1;
		if(index + i < node->entry_active && node->entries[index + i]->key != node->entries[index]->key)
			return index + i;
	}
	return -1;
}

static void esbtree_split_leafnode(esbt_tree * esbtree, bt_node * node)
{
	stat_addnode(esbtree->stat, 0);	
	
	short position = es_get_split_point(esbtree, es_node_trace[0]);
	if(position == -1)
	{
		if(IS_NODE_FULL(esbtree,node))
			node->entry_active--;
		return;
	}

	bt_node * newchild = allocate_btree_node(esbtree->order, 0);
	for(short i = position; i < node->entry_active; i++)
		newchild->entries[i - position] = es_node_trace[0]->entries[i];
	newchild->entry_active = node->entry_active - position;
	es_node_trace[0]->entry_active = position;
	if(esbtree->root->node_level == 0)
	{
		bt_node * newroot = allocate_btree_node(esbtree->order, 1);
		newroot->entry_active = 1;
		newroot->entries[0] = es_node_trace[0]->entries[position];
		newroot->children[0] = es_node_trace[0];
		newroot->children[1] = newchild;
		esbtree->root = newroot;
	}
	else
	{
		esbtree_insert_inner(es_node_trace[1], es_node_trace[0]->entries[position], es_node_trace[0], newchild, 1);

		if(IS_NODE_FULL(esbtree, es_node_trace[1]))
			esbtree_split_innernode(esbtree, 1);
		else if(IS_NODE_HALF_FULL(esbtree, es_node_trace[1]))
		{
			if(need_split(esbtree, 1))
				esbtree_split_innernode(esbtree, 1);
		}
	}

}

static void esbtree_split_innernode(esbt_tree * esbtree, short level)
{
	stat_addnode(esbtree->stat, level);	
	short position = es_get_split_point(esbtree, es_node_trace[level]);
	bt_node * newchild = allocate_btree_node(esbtree->order, level);
	for(short i = position + 1; i < es_node_trace[level]->entry_active; i++)
	{
		newchild->entries[i - position - 1] = es_node_trace[level]->entries[i];
		newchild->children[i - position - 1] = es_node_trace[level]->children[i];
	}
	newchild->children[es_node_trace[level]->entry_active - 1 - position] = es_node_trace[level]->children[es_node_trace[level]->entry_active];

	newchild->entry_active = es_node_trace[level]->entry_active - 1 - position;
	es_node_trace[level]->entry_active = position;

	if(esbtree->root->node_level == level)
	{
		bt_node * newroot = allocate_btree_node(esbtree->order, level + 1);
		newroot->entry_active = 1;
		newroot->entries[0] = es_node_trace[level]->entries[position];
		newroot->children[0] = es_node_trace[level];
		newroot->children[1] = newchild;
		esbtree->root = newroot;	
	}
	else
	{
		esbtree_insert_inner(es_node_trace[level + 1], es_node_trace[level]->entries[position], es_node_trace[level], newchild, level + 1);

		if(IS_NODE_FULL(esbtree, es_node_trace[level + 1]))
			esbtree_split_innernode(esbtree, level + 1);
		else if(IS_NODE_HALF_FULL(esbtree, es_node_trace[level + 1]))
		{
			if(need_split(esbtree, level + 1))
				esbtree_split_innernode(esbtree, level + 1);
		}
	}
}
